package 题目集.动态规划.区间dp;

import org.junit.Test;
import 题目集.滑动窗口.ch02_不定长窗口.ch07_将x减到0的最小操作数;

/**
 * https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/
 * 题目大意：给你一个数组nums，一个数K。你每次可以取数组最左侧或最右侧的一个数，问最少需要取多少次，可以使得取出来的数之和=x
 */
public class demo01_将x减到0的最小操作数 {

    /**
     * 第一思路暴力解：区间dp,有3个参数，左右区间端点，以及要凑成的数k
     * 第三个参数可以优化掉，通过前缀和快速求左右区间的和，来判断是否和为k，这样第三个参数就变成了常量（所以可以去掉）
     * 时间复杂度n^2
     * 第二思路，滑动窗口：{@link ch07_将x减到0的最小操作数#minOperations(int[], int)}
     * @param nums
     * @param k
     * @return
     */
    public int minOperations(int[] nums, int k) {
        n = nums.length;
        this.k = k;
        sum = new int[nums.length + 1];
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        int ans = dfs(1, nums.length);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    int n;
    int[] sum;
    int k;
    static int maxn = (int) (1e5 + 10);

    public int dfs(int l, int r) {
        /*这里有问题*/
        if (l > r) return Integer.MAX_VALUE;
        /*如果此时已经满足了条件*/
        if (sum[l - 1] + sum[n] - sum[r] == k) {
            return 0;
        }
        int left = Integer.MAX_VALUE;
        if (sum[l] + sum[n] - sum[r] <= k) {
            int res = dfs(l + 1, r);
            if (res != Integer.MAX_VALUE) {
                left = res + 1;
            }
        }
        int right = Integer.MAX_VALUE;
        if (sum[l - 1] + sum[n] - sum[r - 1] <= k) {
            int res = dfs(l, r - 1);
            if (res != Integer.MAX_VALUE) {
                right = res + 1;
            }
        }
        return Math.min(left, right);
    }

    @Test
    public void t2() {
        int[] arr = {3, 2, 20, 1, 1, 3};
        int k = 10;
        System.out.println(minOperations(arr, k));
    }

    /**
     * 上一个版本的dfs
     *     int[] nums;
     *
     *     public int dfs(int l, int r, int k) {
     *         if (l > r) return Integer.MAX_VALUE;
     *         if (nums[l] == k || nums[r] == k) {
     *             return 1;
     *         }
     *         int left = Integer.MAX_VALUE;
     *         if (nums[l] < k) {
     *             int res = dfs(l + 1, r, k - nums[l]);
     *             if (res != Integer.MAX_VALUE) {
     *                 left = res + 1;
     *             }
     *         }
     *         int right = Integer.MAX_VALUE;
     *         if (nums[r] < k) {
     *             int res = dfs(l, r - 1, k - nums[r]);
     *             if (res != Integer.MAX_VALUE) {
     *                 right = res + 1;
     *             }
     *         }
     *         return Math.min(left, right);
     *     }
     */

}
